package com.lw.leetcode.back.c;

/**
 * Created with IntelliJ IDEA.
 * back
 * 1601. 最多可达成的换楼请求数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/28 10:19
 */
public class MaximumRequests {

    private int[] delta;
    private int ans = 0;
    private int cnt = 0;
    private int zero;
    private int n;

    public int maximumRequests(int n, int[][] requests) {
        delta = new int[n];
        zero = n;
        this.n = n;
        find(requests, 0);
        return ans;
    }

    public void find(int[][] requests, int pos) {
        if (pos == requests.length) {
            if (zero == n) {
                ans = Math.max(ans, cnt);
            }
            return;
        }
        find(requests, pos + 1);
        int z = zero;
        ++cnt;
        int[] r = requests[pos];
        int x = r[0];
        int y = r[1];
        zero -= delta[x] == 0 ? 1 : 0;
        --delta[x];
        zero += delta[x] == 0 ? 1 : 0;
        zero -= delta[y] == 0 ? 1 : 0;
        ++delta[y];
        zero += delta[y] == 0 ? 1 : 0;
        find(requests, pos + 1);
        --delta[y];
        ++delta[x];
        --cnt;
        zero = z;
    }

}
